package com.faiz.algorithm;

public class NumIslands {
    private int count;
    private boolean[][] visited;
    private int m;
    private int n;

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        count = 0;
        visited = new boolean[m][n];
        dfs(0, 0, grid);
        return count;
    }

    //方法1： 使用深度优先
    private void dfs(int i, int j, char[][] grid) {
        // 如果该点已经被访问，或当前的index越界，则直接返回
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || visited[i][j]) {
            return;
        }
        // 设置该点已经被访问
        visited[i][j] = true;

        if (grid[i][j] == 1) {
            plusCount(i, j, grid);
        }
        dfs(i - 1, j, grid);
        dfs(i, j + 1, grid);
        dfs(i + 1, j, grid);
        dfs(i, j - 1, grid);
    }

    private void plusCount(int i, int j, char[][] grid) {
        switch (grid[i][j]) {
            case 0:
                // 如果当前点的值是0直接返回
                return;
            case 1:
                if (i - 1 >= 0) {
                    if (grid[i - 1][j] == 1 && visited[i - 1][j]) {
                        return;
                    }
                }
                if (j + 1 <= n - 1) {
                    if (grid[i][j + 1] == 1 && visited[i][j + 1]) {
                        return;
                    }
                }
                if (i + 1 <= m - 1) {
                    if (grid[i + 1][j] == 1 && visited[i + 1][j]) {
                        return;
                    }
                }
                if (j - 1 >= 0) {
                    if (grid[i][j - 1] == 1 && visited[i][j - 1]) {
                        return;
                    }
                }
                count++;
        }
    }

    public static void main(String[] args) {
        NumIslands numIslands = new NumIslands();
        char[][] grid = {
                            {1, 1, 1, 1, 0},
                            {1, 1, 0, 1, 0},
                            {1, 1, 0, 0, 0},
                            {0, 0, 0, 0, 0}};
        System.out.println(numIslands.numIslands(grid));
    }
}
